package leetcode.median;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * ClassName: $763_PartitionLabel
 * Description:
 * date: 2021-10-16 23:11
 *
 * @author liyifan
 */
public class $763_PartitionLabel {
    public List<Integer> partitionLabels(String s) {
        // 1.首先得到所有字符的lastIndex
        HashMap<Character, Integer> lastIndexMap = new HashMap<>();
        for (Character c:s.toCharArray()) {
            if (!lastIndexMap.containsKey(c)){
                lastIndexMap.put(c, s.lastIndexOf(c));
            }
        }
        // 2.从头遍历字符串，对于每个片段的第一个字母c，暂时定片段长为 lastIndex(c) - current_index
        // 3.对于后面的每个字符x 如果lastIndex(x) > lastIndex(c) 更新片段长度
        // 4.到最后一个字符 如果全部完成 就res++
        // ababcbacadefegdehijhklij
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0;i < s.length();) {
            int lastIndex = lastIndexMap.get(s.charAt(i));
            // System.out.println("start char: " + s.charAt(i));
            for (int j = i;j <= lastIndex;j++) {
                // System.out.println("lastIndex: " + lastIndex);
                if (lastIndexMap.get(s.charAt(j)) > lastIndex) {
                    // System.out.println("expand: " + j);
                    lastIndex = lastIndexMap.get(s.charAt(j));
                }
            }
            res.add(lastIndex - i + 1);
            i = res.get(res.size() - 1) + i;
            // System.out.println(i);
        }
        return res;
    }
}
